package leetcode.year2021.month11;

import java.lang.reflect.Array;
import java.util.*;

// 448. 找到所有数组中消失的数字
public class _12_5FindDisappearedNumbers448 {
  public List<Integer> findDisappearedNumbers(int[] nums) {
    // 又来了，原地哈希
    // 当然，先借助Set简单实现先
    // 方法1，使用Set
    ArrayList<Integer> result = new ArrayList<>();

    int n = nums.length;

    for (int i = 0; i < n; i++) {
      while ( i>= 0 && i < n && nums[i] != nums[nums[i]-1]){
        swap(nums,i,nums[i]-1);
      }
    }

    for (int i = 0; i < n; i++) {
      if (i != nums[i]-1){
        result.add(i+1);
      }
    }

    return result;

//    ArrayList<Integer> res = new ArrayList<>();
//    HashSet<Integer> numSet = new HashSet<>();
//    for (int i = 0; i < nums.length; i++) {
//      numSet.add(nums[i]);
//    }
//    for (int i = 1; i <= nums.length; i++) {
//      if (!numSet.contains(i)){
//        res.add(i);
//      }
//    }
//    return res;
  }

  private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }

  /**
   * 448. 找到所有数组中消失的数字
   * 给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
   *
   *
   *
   * 示例 1：
   *
   * 输入：nums = [4,3,2,7,8,2,3,1]
   * 输出：[5,6]
   * 示例 2：
   *
   * 输入：nums = [1,1]
   * 输出：[2]
   *
   *
   * 提示：
   *
   * n == nums.length
   * 1 <= n <= 105
   * 1 <= nums[i] <= n
   * 进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
   *
   * 通过次数143,941提交次数221,602
   */
}
